//
//  main.c
//  折半查找
//
//  Created by ws on 2017/7/20.
//  Copyright © 2017年 王松. All rights reserved.
//

#include <stdio.h>

/*
 从一个有序数组中找出值所对应的下标，如果找到了就返回那个下标，如果没有找到就返回-1
 */

/*
 折半查找
 */

int binarySearch(int array[],int count,int key)
{
    //  定义一个变量记录最大值下标
    int max = count - 1;
    
    //  定义一个变量记录最小值下标
    int min = 0;
    //  当min < max 就进行循环
    
    int aim = -1;
    
    while (min <= max) {
        //      计算中间下标
        int mid = (min + max) / 2;
        
        if (array[mid] == key) {
            //            return mid;
            aim = mid;
            break;
            //        如果猜大了就调整max
        }else if (array[mid] > key){
            max = mid - 1;
        }else{
            min = mid + 1;
        }
        
    }
    
    return aim;
}


/*
 折半查找练习
 
 向一个有序数组中插入某个值，插入之后数组依然是有序，找出插入的这个值位置(下标)
 
 */

int positionOfInsert(int array[],int count,int insertedKey){
    // 定义变量记录最大值的下标
    int max = count - 1;
    // 最小下标
    int min = 0;
    // 循环去找插入的位置
    while (min <= max) {
        // 计算中间的下标
        int mid = (min + max) / 2;
        if(array[mid] == insertedKey){
            return mid;
        }else if(array[mid] > insertedKey){
            max = mid - 1;
        }else{
            min = mid + 1;
        }
    }
    //  如果没有找到那么min就是要插入的位置
    return min;
}




int main(int argc, const char * argv[]) {
    
    int nums[] = {2,6,7,8,9};
    
    int key = 1;
    
    int count = sizeof(nums) / sizeof(int);
    
    //    int aim = binarySearch(nums,count,key);
    
    int insertPosition = positionOfInsert(nums, count, key);
    
    printf("%d 在数组中下标为 %d\n",key,insertPosition);
    
    return 0;
}
